public class BracketMatch {

    private class Node {
        Node next;
        char bracket;

        Node() {}
        Node(char bracket) {
            this.bracket = bracket;
            this.next = null;
        }
    }

    private Node head;
    private Node top;
    private int len;

    BracketMatch() {
        this.len = 0;
    }

    private void push(char bracket) {
        Node node = new Node(bracket);
        if (this.len == 0) {
            this.top = node;
            this.head = node;
        } else {
            this.top.next = node;
            this.top = node;
        }
        this.len ++;
    }

    private Node pop() {
        Node node;
        if (this.len == 0) {
            System.out.println("warning: 栈内无可pop的元素");
            return null;
        } else if (this.len == 1) {
            node = this.top;
            this.top = null; // mark here
            this.head = null;
        } else {
            node = this.top;
            this.top = this.traverse();
        }
        this.len --;
        return node;
    }

    private Node traverse() {
        Node node = this.head;
        for (int i = 1; i < this.len-1; i ++){
            node = node.next;
        }
        return node;
    }

    public void show() {
        Node node = this.head;
        System.out.print("栈内元素有: [");
        for (int i = 0; i < this.len; i++) {
            System.out.printf("-'%c'-", node.bracket);
            node = node.next;
        }
        System.out.println("]");
    }

    public int len() {
        return this.len;
    }

    public boolean isEmpty() {
        return this.len == 0;
    }

    private int bracketType(char bracket) {
        char[] left_bracket = {'(', '[', '{'};
        char[] right_bracket = {')', ']', '}'};
        for (int i = 0; i < left_bracket.length; i ++) {
            if (bracket == left_bracket[i]) {
                return 0;
            }
        }
        for (int i = 0; i < right_bracket.length; i ++) {
            if (bracket == right_bracket[i]) {
                return 1;
            }
        }
        return -1;
    }

    private boolean isBracketPair(char stackBracket, char bracket) {
        char[][] bracketPair = {{'(', ')'}, {'[', ']'}, {'{', '}'}};
        for (int i = 0; i < bracketPair.length; i ++) {
            if (stackBracket == bracketPair[i][0]) {
                if (bracket == bracketPair[i][1]) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean checkMatch(char bracket) {
        if (this.bracketType(bracket) == 0) { // 左括号入栈
            System.out.printf("此为左括号，push括号%c\n", bracket);
            this.push(bracket);
            this.show();
            return true;
        } else if (this.bracketType(bracket) == 1 && this.len == 0) {
            System.out.println("error: 与栈顶左括号不匹配");
            return false;
        } else if (this.bracketType(bracket) == 1 && this.len != 0) { // 右括号匹配
            Node node = this.top;
            if (this.isBracketPair(node.bracket, bracket)) {
                System.out.printf("此为右括号，匹配栈顶括号，pop左括号%c\n", this.top.bracket);
                this.pop();
                this.show();
                return true;
            } else {
                System.out.println("error: 与栈顶左括号不匹配");
                return false;
            }
        } else {
            System.out.println("error: 非{}[]()括号，不可匹配");
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println("Bracket Match started...");
        char[] brackets = {'[', '{', '(', ')', '}', ']', '[', ']', '(', ')', '{', '}', '('};
        BracketMatch bracketMatch = new BracketMatch();
        for (int i = 0; i < brackets.length; i ++) {
            System.out.printf("开始检查括号: %c\n", brackets[i]);
            if(bracketMatch.checkMatch(brackets[i])) {
                continue;
            } else {
                System.out.println("------匹配失败-----");
                break;
            }
        }
    }

}
